/*
 * @lc app=leetcode.cn id=52 lang=cpp
 *
 * [52] N 皇后 II
 */
#include <vector>

// @lc code=start
class Solution
{
  private:
    void totalNQueens_dfs(int n, int row, std::vector<bool> &cols, std::vector<bool> &diagonal1, std::vector<bool> &diagonal2, int &total)
    {
        if (row == n) {
            ++total;
        }

        for (int col = 0; col < n; ++col) {
            int main_diagonal = row - col + (n - 1);
            int counter_diagonal = row + col;
            if (!cols[col] && !diagonal1[main_diagonal] && !diagonal2[counter_diagonal]) {
                cols[col] = diagonal1[main_diagonal] = diagonal2[counter_diagonal] = true;
                totalNQueens_dfs(n, row + 1, cols, diagonal1, diagonal2, total);
                cols[col] = diagonal1[main_diagonal] = diagonal2[counter_diagonal] = false;
            }
        }
    }

  public:
    int totalNQueens(int n)
    {
        std::vector<bool> cols(n, false);
        std::vector<bool> diagonal1(2 * n - 1, false);
        std::vector<bool> diagonal2(2 * n - 1, false);
        int total = 0;
        totalNQueens_dfs(n, 0, cols, diagonal1, diagonal2, total);
        return total;
    }
};
// @lc code=end
